package XiaoMi;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 求两个数组的非公共部分元素
 *
 * @leiwenkang 2018-03-01 20:03.
 */
public class Test {
    public static void main(String[] args) {
        List<String> list1 = Arrays.asList("a", "a", "b", "c", "c", "d", "e");
        List<String> list2 = Arrays.asList("a", "b", "b", "d", "f", "f");
        List<String> result = getNotCommonList3(list1, list2);
        if (result != null && !result.isEmpty()) {
            for (String str : result) {
                System.out.println(str);
            }
        }
    }

    //方法1 先求出list1中不在list2的元素，再求出list2中不在list1的元素
    public static List<String> getNotCommonList(List<String> list1, List<String> list2) {
        if (list1 == null || list1.isEmpty()) {
            return list2;
        }
        if (list2 == null || list2.isEmpty()) {
            return list1;
        }
        List<String> notCommonList = new ArrayList<>();
        for (String str : list2) {
            if (!list1.contains(str)) {
                notCommonList.add(str);
            }
        }
        for (String str : list1) {
            if (!list2.contains(str)) {
                notCommonList.add(str);
            }
        }
        return notCommonList;
    }

    //方法2 先求出两个集合交集，再在合并时去除交集元素
    public static List<String> getNotCommonList2(List<String> list1, List<String> list2) {
        if (list1 == null || list1.isEmpty()) {
            return list2;
        }
        if (list2 == null || list2.isEmpty()) {
            return list1;
        }

        Set<String> commonSet = new HashSet<>();
        //求交集
        for (String str : list2) {
            if (list1.contains(str)) {//这里可以把list1中元素先放入set中，用set.contains（）比较来优化效率
                commonSet.add(str);
            }
        }

        List<String> notCommonList = new ArrayList<>();
        for (String str : list1) {
            if (!commonSet.contains(str)) {
                notCommonList.add(str);
            }
        }

        for (String str : list2) {
            if (!commonSet.contains(str)) {
                notCommonList.add(str);
            }
        }

        return notCommonList;
    }


    //优化方法2 再求交集时，遍历的数组选择元素个数较少的数组
    public static List<String> getNotCommonList3(List<String> list1, List<String> list2) {
        if (list1 == null || list1.isEmpty()) {
            return list2;
        }
        if (list2 == null || list2.isEmpty()) {
            return list1;
        }

        List<String> longList = list1;
        List<String> shortList = list2;
        if (list1.size() < list2.size()) {
            longList = list2;
            shortList = list1;
        }
        //进一步优化，把longList先放入set中
        Set<String> longSet = new HashSet<>();
        for (String str : longList) {
            longSet.add(str);
        }

        Set<String> commonSet = new HashSet<>();
        //求交集
        for (String str : shortList) {
            if (longSet.contains(str)) {//这里可以把list1中元素先放入set中，用set.contains（）比较来优化效率
                commonSet.add(str);
            }
        }

        List<String> notCommonList = new ArrayList<>();
        for (String str : list1) {
            if (!commonSet.contains(str)) {
                notCommonList.add(str);
            }
        }

        for (String str : list2) {
            if (!commonSet.contains(str)) {
                notCommonList.add(str);
            }
        }

        return notCommonList;
    }


    private Set<String> getCommonSet(List<String> list1, List<String> list2){
        List<String> longList = list1;
        List<String> shortList = list2;
        if (list1.size() < list2.size()) {
            longList = list2;
            shortList = list1;
        }
        //进一步优化，把longList先放入set中
        Set<String> longSet = new HashSet<>();
        for (String str : longList) {
            longSet.add(str);
        }

        Set<String> commonSet = new HashSet<>();
        //求交集
        for (String str : shortList) {
            if (longSet.contains(str)) {//这里可以把list1中元素先放入set中，用set.contains（）比较来优化效率
                commonSet.add(str);
            }
        }
        return commonSet;
    }
}
